﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DiscoveryLogic.Common.Numeric
{
    /// <summary>Abstract base class for resizable lists holding objects or primitive data types such as <code>int</code>, <code>float</code>, etc.
    /// First see the <a href="package-summary.html">package summary</a> and javadoc <a href="package-tree.html">tree view</a> to get the broad picture.
    /// </summary>
    [Serializable]
    public abstract class AbstractList : AbstractCollection
    {
        /// <summary> Sets the size of the receiver.
        /// If the new size is greater than the current size, new null or zero items are added to the end of the receiver.
        /// If the new size is less than the current size, all components at index newSize and greater are discarded.
        /// This method does not release any superfluos internal memory. Use method <tt>trimToSize</tt> to release superfluos internal memory.
        /// </summary>
        /// <param name="newSize">the new size of the receiver.
        /// </param>
        /// <throws>  IndexOutOfBoundsException if <tt>newSize &lt; 0</tt>. </throws>
        virtual public int Size
        {
            set
            {
                if (value < 0)
                    throw new System.IndexOutOfRangeException("newSize:" + value);

                int currentSize = size();
                if (value != currentSize)
                {
                    if (value > currentSize)
                        beforeInsertDummies(currentSize, value - currentSize);
                    else if (value < currentSize)
                        removeFromTo(value, currentSize - 1);
                }
            }

        }
        /// <summary> Makes this class non instantiable, but still let's others inherit from it.</summary>
        protected internal AbstractList()
        {
        }
        /// <summary> Appends all of the elements of the specified Collection to the
        /// receiver.
        /// 
        /// </summary>
        /// <exception cref="ClassCastException">if an element in the collection is not
        /// of the same parameter type of the receiver.
        /// </exception>
        public virtual void addAllOf(System.Collections.ICollection collection)
        {
            this.beforeInsertAllOf(size(), collection);
        }
        /// <summary>Inserts all elements of the specified collection before the specified position into the receiver. 
        /// Shifts the element
        /// currently at that position (if any) and any subsequent elements to
        /// the right (increases their indices). 
        /// 
        /// </summary>
        /// <param name="index">index before which to insert first element from the specified collection.
        /// </param>
        /// <param name="collection">the collection to be inserted
        /// </param>
        /// <exception cref="ClassCastException">if an element in the collection is not
        /// of the same parameter type of the receiver.
        /// </exception>
        /// <throws>  IndexOutOfBoundsException if <tt>index &lt; 0 || index &gt; size()</tt>. </throws>
        public virtual void beforeInsertAllOf(int index, System.Collections.ICollection collection)
        {
            this.beforeInsertDummies(index, collection.Count);
            this.replaceFromWith(index, collection);
        }
        /// <summary> Inserts <tt>length</tt> dummy elements before the specified position into the receiver. 
        /// Shifts the element currently at that position (if any) and
        /// any subsequent elements to the right.
        /// <b>This method must set the new size to be <tt>size()+length</tt>.
        /// 
        /// </summary>
        /// <param name="index">index before which to insert dummy elements (must be in [0,size])..
        /// </param>
        /// <param name="length">number of dummy elements to be inserted.
        /// </param>
        /// <throws>  IndexOutOfBoundsException if <tt>index &lt; 0 || index &gt; size()</tt>. </throws>
        protected internal abstract void beforeInsertDummies(int index, int length);
        /// <summary> Checks if the given index is in range.</summary>
        protected internal static void checkRange(int index, int theSize)
        {
            if (index >= theSize || index < 0)
                throw new System.IndexOutOfRangeException("Index: " + index + ", Size: " + theSize);
        }
        /// <summary> Checks if the given range is within the contained array's bounds.</summary>
        /// <throws>  IndexOutOfBoundsException if <tt>to!=from-1 || from&lt;0 || from&gt;to || to&gt;=size()</tt>. </throws>
        protected internal static void checkRangeFromTo(int from, int to, int theSize)
        {
            if (to == from - 1)
                return;
            if (from < 0 || from > to || to >= theSize)
                throw new System.IndexOutOfRangeException("from: " + from + ", to: " + to + ", size=" + theSize);
        }
        /// <summary> Removes all elements from the receiver.  The receiver will
        /// be empty after this call returns, but keep its current capacity.
        /// </summary>
        public override void clear()
        {
            removeFromTo(0, size() - 1);
        }
        /// <summary> Sorts the receiver into ascending order.  
        /// This sort is guaranteed to be <i>stable</i>:  equal elements will
        /// not be reordered as a result of the sort.<p>
        /// 
        /// The sorting algorithm is a modified mergesort (in which the merge is
        /// omitted if the highest element in the low sublist is less than the
        /// lowest element in the high sublist).  This algorithm offers guaranteed
        /// n*log(n) performance, and can approach linear performance on nearly
        /// sorted lists.
        /// 
        /// <p><b>You should never call this method unless you are sure that this particular sorting algorithm is the right one for your data set.</b>
        /// It is generally better to call <tt>sort()</tt> or <tt>sortFromTo(...)</tt> instead, because those methods automatically choose the best sorting algorithm.
        /// </summary>
        public void mergeSort()
        {
            mergeSortFromTo(0, size() - 1);
        }
        /// <summary> Sorts the receiver into ascending order.  
        /// This sort is guaranteed to be <i>stable</i>:  equal elements will
        /// not be reordered as a result of the sort.<p>
        /// 
        /// The sorting algorithm is a modified mergesort (in which the merge is
        /// omitted if the highest element in the low sublist is less than the
        /// lowest element in the high sublist).  This algorithm offers guaranteed
        /// n*log(n) performance, and can approach linear performance on nearly
        /// sorted lists.
        /// 
        /// <p><b>You should never call this method unless you are sure that this particular sorting algorithm is the right one for your data set.</b>
        /// It is generally better to call <tt>sort()</tt> or <tt>sortFromTo(...)</tt> instead, because those methods automatically choose the best sorting algorithm.
        /// 
        /// </summary>
        /// <param name="from">the index of the first element (inclusive) to be sorted.
        /// </param>
        /// <param name="to">the index of the last element (inclusive) to be sorted.
        /// </param>
        /// <throws>  IndexOutOfBoundsException if <tt>(from&lt;0 || from&gt;to || to&gt;=size()) && to!=from-1</tt>. </throws>
        public abstract void mergeSortFromTo(int from, int to);
        /// <summary> Sorts the receiver into
        /// ascending order.  The sorting algorithm is a tuned quicksort,
        /// adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a
        /// Sort Function", Software-Practice and Experience, Vol. 23(11)
        /// P. 1249-1265 (November 1993).  This algorithm offers n*log(n)
        /// performance on many data sets that cause other quicksorts to degrade to
        /// quadratic performance.
        /// 
        /// <p><b>You should never call this method unless you are sure that this particular sorting algorithm is the right one for your data set.</b>
        /// It is generally better to call <tt>sort()</tt> or <tt>sortFromTo(...)</tt> instead, because those methods automatically choose the best sorting algorithm.
        /// </summary>
        public void quickSort()
        {
            quickSortFromTo(0, size() - 1);
        }
        /// <summary> Sorts the specified range of the receiver into
        /// ascending order.  The sorting algorithm is a tuned quicksort,
        /// adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a
        /// Sort Function", Software-Practice and Experience, Vol. 23(11)
        /// P. 1249-1265 (November 1993).  This algorithm offers n*log(n)
        /// performance on many data sets that cause other quicksorts to degrade to
        /// quadratic performance.
        /// 
        /// <p><b>You should never call this method unless you are sure that this particular sorting algorithm is the right one for your data set.</b>
        /// It is generally better to call <tt>sort()</tt> or <tt>sortFromTo(...)</tt> instead, because those methods automatically choose the best sorting algorithm.
        /// 
        /// </summary>
        /// <param name="from">the index of the first element (inclusive) to be sorted.
        /// </param>
        /// <param name="to">the index of the last element (inclusive) to be sorted.
        /// </param>
        /// <throws>  IndexOutOfBoundsException if <tt>(from&lt;0 || from&gt;to || to&gt;=size()) && to!=from-1</tt>. </throws>
        public abstract void quickSortFromTo(int from, int to);
        /// <summary> Removes the element at the specified position from the receiver.
        /// Shifts any subsequent elements to the left.
        /// 
        /// </summary>
        /// <param name="index">the index of the element to removed.
        /// </param>
        /// <throws>  IndexOutOfBoundsException if <tt>index &lt; 0 || index &gt;= size()</tt>. </throws>
        public virtual void remove(int index)
        {
            removeFromTo(index, index);
        }
        /// <summary> Removes from the receiver all elements whose index is between
        /// <code>from</code>, inclusive and <code>to</code>, inclusive.  Shifts any succeeding
        /// elements to the left (reduces their index).
        /// This call shortens the list by <tt>(to - from + 1)</tt> elements.
        /// 
        /// </summary>
        /// <param name="from">index of first element to be removed.
        /// </param>
        /// <param name="to">index of last element to be removed.
        /// </param>
        /// <throws>  IndexOutOfBoundsException if <tt>(from&lt;0 || from&gt;to || to&gt;=size()) && to!=from-1</tt>. </throws>
        public abstract void removeFromTo(int fromIndex, int toIndex);
        /// <summary> Replaces the part of the receiver starting at <code>from</code> (inclusive) with all the elements of the specified collection.
        /// Does not alter the size of the receiver.
        /// Replaces exactly <tt>Math.max(0,Math.min(size()-from, other.size()))</tt> elements.
        /// 
        /// </summary>
        /// <param name="from">the index at which to copy the first element from the specified collection.
        /// </param>
        /// <param name="other">Collection to replace part of the receiver
        /// </param>
        /// <throws>  IndexOutOfBoundsException if <tt>index &lt; 0 || index &gt;= size()</tt>. </throws>
        public abstract void replaceFromWith(int from, System.Collections.ICollection other);
        /// <summary> Reverses the elements of the receiver.
        /// Last becomes first, second last becomes second first, and so on.
        /// </summary>
        public abstract void reverse();
        /// <summary> Randomly permutes the receiver. After invocation, all elements will be at random positions.</summary>
        public void shuffle()
        {
            shuffleFromTo(0, size() - 1);
        }
        /// <summary> Randomly permutes the receiver between <code>from</code> (inclusive) and <code>to</code> (inclusive). </summary>
        /// <param name="from">the start position (inclusive)
        /// </param>
        /// <param name="to">the end position (inclusive)
        /// </param>
        /// <throws>  IndexOutOfBoundsException if <tt>(from&lt;0 || from&gt;to || to&gt;=size()) && to!=from-1</tt>. </throws>
        public abstract void shuffleFromTo(int from, int to);
        /// <summary> Sorts the receiver into ascending order. 
        /// 
        /// The sorting algorithm is dynamically chosen according to the characteristics of the data set.
        /// 
        /// This implementation simply calls <tt>sortFromTo(...)</tt>.
        /// Override <tt>sortFromTo(...)</tt> if you can determine which sort is most appropriate for the given data set.
        /// </summary>
        public void sort()
        {
            sortFromTo(0, size() - 1);
        }
        /// <summary> Sorts the specified range of the receiver into ascending order. 
        /// 
        /// The sorting algorithm is dynamically chosen according to the characteristics of the data set.
        /// This default implementation simply calls quickSort.
        /// Override this method if you can determine which sort is most appropriate for the given data set.
        /// 
        /// </summary>
        /// <param name="from">the index of the first element (inclusive) to be sorted.
        /// </param>
        /// <param name="to">the index of the last element (inclusive) to be sorted.
        /// </param>
        /// <throws>  IndexOutOfBoundsException if <tt>(from&lt;0 || from&gt;to || to&gt;=size()) && to!=from-1</tt>. </throws>
        public virtual void sortFromTo(int from, int to)
        {
            quickSortFromTo(from, to);
        }
        /// <summary> Trims the capacity of the receiver to be the receiver's current 
        /// size. Releases any superfluos internal memory. An application can use this operation to minimize the 
        /// storage of the receiver.
        /// <p>
        /// This default implementation does nothing. Override this method in space efficient implementations.
        /// </summary>
        public virtual void trimToSize()
        {
        }
    }
}
